{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count of Sub-Multisets With Bounded Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #dynamic-programming #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #动态规划 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSubMultisets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #和带限制的子多重集合的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的非负整数数组&nbsp;<code>nums</code>&nbsp;和两个整数&nbsp;<code>l</code> 和&nbsp;<code>r</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回&nbsp;<code>nums</code>&nbsp;中子多重集合的和在闭区间&nbsp;<code>[l, r]</code>&nbsp;之间的 <strong>子多重集合的数目</strong> 。</p>\n",
    "\n",
    "<p>由于答案可能很大，请你将答案对&nbsp;<code>10<sup>9 </sup>+ 7</code>&nbsp;取余后返回。</p>\n",
    "\n",
    "<p><strong>子多重集合</strong> 指的是从数组中选出一些元素构成的 <strong>无序</strong>&nbsp;集合，每个元素 <code>x</code>&nbsp;出现的次数可以是&nbsp;<code>0, 1, ..., occ[x]</code>&nbsp;次，其中&nbsp;<code>occ[x]</code>&nbsp;是元素&nbsp;<code>x</code>&nbsp;在数组中的出现次数。</p>\n",
    "\n",
    "<p><b>注意：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果两个子多重集合中的元素排序后一模一样，那么它们两个是相同的&nbsp;<strong>子多重集合</strong>&nbsp;。</li>\n",
    "\t<li><strong>空</strong>&nbsp;集合的和是 <code>0</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,2,3], l = 6, r = 6\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>唯一和为 6 的子集合是 {1, 2, 3} 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,1,4,2,7], l = 1, r = 5\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>和在闭区间 [1, 5] 之间的子多重集合为 {1} ，{2} ，{4} ，{2, 2} ，{1, 2} ，{1, 4} 和 {1, 2, 2} 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,1,3,5,2], l = 3, r = 5\n",
    "<b>输出：</b>9\n",
    "<b>解释：</b>和在闭区间 [3, 5] 之间的子多重集合为 {3} ，{5} ，{1, 2} ，{1, 3} ，{2, 2} ，{2, 3} ，{1, 1, 2} ，{1, 1, 3} 和 {1, 2, 2} 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>nums</code> 的和不超过&nbsp;<code>2 * 10<sup>4</sup></code> 。</li>\n",
    "\t<li><code>0 &lt;= l &lt;= r &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-of-sub-multisets-with-bounded-sum](https://leetcode.cn/problems/count-of-sub-multisets-with-bounded-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-of-sub-multisets-with-bounded-sum](https://leetcode.cn/problems/count-of-sub-multisets-with-bounded-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,2,3]\\n6\\n6', '[2,1,4,2,7]\\n1\\n5', '[1,2,1,3,5,2]\\n3\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n",
    "        ans = [0] * (r + 1)\n",
    "        ans[0] = 1\n",
    "        c = Counter(nums)\n",
    "        for k, v in c.items():\n",
    "            if k == 0:\n",
    "                for j in range(len(ans)):\n",
    "                    ans[j] = (ans[j] * (v + 1)) % 1000000007\n",
    "            else:\n",
    "                for j in range(len(ans) - k):\n",
    "                    ans[j + k] = (ans[j + k] + ans[j]) % 1000000007\n",
    "                kv = k * (v + 1)\n",
    "                for j in range(len(ans) - kv - 1, -1, -1):\n",
    "                    ans[j + kv] = (ans[j + kv] - ans[j]) % 1000000007\n",
    "        return sum(ans[l:r+1]) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod=10**9+7\n",
    "class Solution:\n",
    "    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n",
    "        c=list(Counter(nums).items())\n",
    "        f=[0]*(r+1)\n",
    "        f[0]=1\n",
    "        #O(100v)\n",
    "        for i,(x,y) in enumerate(c):\n",
    "            g=[0]*(r+1)\n",
    "            for v in range(r+1):\n",
    "                g[v]=f[v]\n",
    "                if x==0:\n",
    "                    g[v]+=y*f[v]\n",
    "                else:\n",
    "                    if v>=x:\n",
    "                        g[v]+=g[v-x]\n",
    "                    if v-(y+1)*x>=0:\n",
    "                        g[v]-=f[v-(y+1)*x]\n",
    "                g[v]%=mod\n",
    "            f=g\n",
    "        return sum(f[l:r+1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        #好像是在找子集，多重背包\n",
    "        cnt=Counter(nums)\n",
    "\n",
    "        #dfs(i,j)=dfs(i-1,j)+dfs(i-1,j-x)+...+dfs(i-1,j-c*x)\n",
    "        #其中，cnt[x]=c,x在cnt中排在第i个位置\n",
    "        #前缀和优化呼之欲出\n",
    "        #定义s[j]=f[i-1][j]+f[i-1][j-x]+....,这个叫做同余前缀和,两个式子应保持等长\n",
    "        #那么s[j]=s[j-x]+f[i-1][j]\n",
    "        #f[i][j]=s[j]-s[j-(c+1)*x]\n",
    "\n",
    "        #i的范围会是多少?sqrt(S)\n",
    "        \n",
    "        #什么样的前缀和?\n",
    "        #dfs(i,j-x)=dfs(i-1,j-x)+...+dfs(i-1,j-(c+1)*x)\n",
    "\n",
    "        #dfs(i,j)=dfs(i,j-x)+dfs(i-1,j)-dfs(i-1,j-(c+1)*x)\n",
    "\n",
    "        #还有个要点，元素0怎么处理？\n",
    "        MOD=10**9+7\n",
    "        c0=cnt[0]+1\n",
    "        del cnt[0]\n",
    "        s=sum(nums)\n",
    "        '''\n",
    "        @cache\n",
    "        def dfs(i:int,j:int)->int:\n",
    "            if i==-1:\n",
    "                return c0 if j==0 else 0\n",
    "            if j<0:\n",
    "                return 0\n",
    "            x,c=s[i]\n",
    "            return (dfs(i,j-x)+dfs(i-1,j)-dfs(i-1,j-(c+1)*x))%MOD\n",
    "        '''\n",
    "        \n",
    "        '''\n",
    "        f=[[0]*(s+1) for _ in range(len(cnt)+1)]\n",
    "        f[0][0]=c0\n",
    "        for i,(x,c) in enumerate(cnt.items()):\n",
    "            for j in range(s+1):\n",
    "                if j<x:\n",
    "                    f[i+1][j]=f[i][j]\n",
    "                else:\n",
    "                    if j-(c+1)*x<0:\n",
    "                        f[i+1][j]=(f[i+1][j-x]+f[i][j])%MOD\n",
    "                    else:\n",
    "                        f[i+1][j]=(f[i+1][j-x]+f[i][j]-f[i][j-(c+1)*x])%MOD\n",
    "        \n",
    "        return sum(f[-1][l:r+1])%MOD\n",
    "        '''\n",
    "\n",
    "        '''\n",
    "        f=[c0]+[0]*(s)\n",
    "        for i,(x,c) in enumerate(cnt.items()):\n",
    "            new_f=f.copy()\n",
    "            for j in range(x,s+1):\n",
    "                if j-(c+1)*x<0:\n",
    "                        new_f[j]=(new_f[j-x]+f[j])%MOD\n",
    "                else:\n",
    "                    new_f[j]=(new_f[j-x]+f[j]-f[j-(c+1)*x])%MOD\n",
    "            f=new_f\n",
    "        return sum(f[l:r+1])%MOD\n",
    "        '''\n",
    "\n",
    "        #问题来了，这个x是谁的x？，显然，它是当前的x，与上一个无关\n",
    "        #定义s[j]=f[i-1][j]+f[i-1][j-x]+....,这个叫做同余前缀和,两个式子应保持等长\n",
    "        #那么s[j]=s[j-x]+f[i-1][j]\n",
    "        #f[i][j]=s[j]-s[j-(c+1)*x]\n",
    "\n",
    "        '''\n",
    "        f=[[0]*(s+1) for _ in range(len(cnt)+1)]\n",
    "        f[0][0]=c0\n",
    "        for i,(x,c) in enumerate(cnt.items()):\n",
    "            p=f[i].copy()\n",
    "            for j in range(x,s+1):\n",
    "                p[j]=p[j-x]+f[i][j]\n",
    "            for j in range(s+1):\n",
    "                if j-(c+1)*x>=0:\n",
    "                    f[i+1][j]=p[j]-p[j-(c+1)*x]\n",
    "                else:\n",
    "                    f[i+1][j]=p[j]\n",
    "        return sum(f[-1][l:r+1])%MOD\n",
    "        '''\n",
    "\n",
    "        f=[0]*(s+1)\n",
    "        f[0]=c0\n",
    "        for i,(x,c) in enumerate(cnt.items()):\n",
    "            p=f.copy()\n",
    "            for j in range(x,s+1):\n",
    "                p[j]=p[j-x]+f[j]\n",
    "            for j in range(s+1):\n",
    "                if j-(c+1)*x>=0:\n",
    "                    f[j]=p[j]-p[j-(c+1)*x]\n",
    "                else:\n",
    "                    f[j]=p[j]\n",
    "        return sum(f[l:r+1])%MOD\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n",
    "        total = sum(nums)\n",
    "        cnt = Counter(nums)\n",
    "        zeros = cnt[0]\n",
    "        del cnt[0]\n",
    "        dic = Counter()\n",
    "        dic[0] = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        res = 0\n",
    "        for key, val in cnt.items():\n",
    "            new_dic = dic.copy()\n",
    "            for i in range(key, 2 * key):\n",
    "                x = 0\n",
    "                for j in range(i, total+1, key):\n",
    "                    x += dic[j-key]\n",
    "                    if j - key*(val+1) >= 0:\n",
    "                        x -= dic[j - key*(val+1)]\n",
    "                    new_dic[j] += x\n",
    "            dic = new_dic\n",
    "        for i in range(l, r+1):\n",
    "            res += dic[i]\n",
    "            res %= mod\n",
    "        res *= zeros + 1\n",
    "        return res % mod\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n",
    "        c = Counter(nums)\n",
    "        nums = sorted(set(nums), key=lambda x: -x)\n",
    "\n",
    "        n = len(c) - (0 in c)\n",
    "        dp = defaultdict(int)\n",
    "        dp[0] = c[0] + 1\n",
    "        del c[0]\n",
    "\n",
    "        \n",
    "        for index in range(n):\n",
    "            curDp = defaultdict(int)\n",
    "            item = nums[index]\n",
    "            ct = c[item]\n",
    "            for d in range(r + 1):\n",
    "      \n",
    "                curDp[d] = (dp[d] +\n",
    "                            (curDp[d - item] if d >= item else 0) -\n",
    "                            (dp[d - (ct + 1) * item] if d - (ct + 1) * item >= 0 else 0)) \n",
    "            dp = curDp\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(l, r + 1):\n",
    "            res += dp[i]\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n",
    "        MOD = 1000000007\n",
    "        if sum(nums)<l:\n",
    "            return 0\n",
    "\n",
    "        d = Counter(nums)\n",
    "        vocab = list(d.items())\n",
    "        \n",
    "        # vocab = sorted((k,v) for k,v in d.items())\n",
    "        # print(vocab)\n",
    "            \n",
    "        dp = defaultdict(int)\n",
    "        dp[0]=d[0]+1\n",
    "        ub=0\n",
    "        for i, (num, n) in enumerate(vocab):\n",
    "            if num==0:\n",
    "                continue\n",
    "            ub = min(r,ub+n*num)\n",
    "            dp_new = defaultdict(int)              \n",
    "            for m in range(ub+1):\n",
    "                dp_new[m]=dp_new[m-num] +dp[m]-dp[m-(n+1)*num]\n",
    "                dp_new[m] % MOD            \n",
    "            \n",
    "            dp = dp_new\n",
    "            # print(i,num, n, dp)\n",
    "            \n",
    "        return sum(dp[k] for k in dp if l<=k<=r)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "M = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n",
    "        S = sum(nums)\n",
    "        a = np.zeros(S + 1, np.int32)\n",
    "        a[0] = 1\n",
    "        cnt = Counter(nums)\n",
    "        for x, c in cnt.items():\n",
    "            if x == 0: continue\n",
    "            b = a.copy()\n",
    "            for i in range(1, 1 + c):\n",
    "                y = x * i\n",
    "                a[y:] += b[:S + 1 - y]\n",
    "                a[y:] %= M\n",
    "        return int(sum(a[l : r + 1]) * (cnt[0] + 1) % M)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "def mul(x, y):\n",
    "    n = 2 * len(x) - 1\n",
    "    X = np.fft.rfft(x, n)\n",
    "    Y = np.fft.rfft(y, n)\n",
    "    return np.rint(np.fft.irfft(X * Y, n))\n",
    "class Solution:\n",
    "    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n",
    "        c = Counter(nums)\n",
    "        dp = [0] * (r + 1)\n",
    "        dp[0] = c[0] + 1\n",
    "        for i, j in c.items():\n",
    "            if i == 0:\n",
    "                continue\n",
    "            f = [0] * (r + 1)\n",
    "            for x in range(j + 1):\n",
    "                if i * x <= r:\n",
    "                    f[i * x] = 1\n",
    "            dp = mul(dp, f)[:r + 1]\n",
    "            for i in range(len(dp)):\n",
    "                dp[i] = dp[i] % int(1e9 + 7)\n",
    "        return int(sum(dp[l:])) % int(1e9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n",
    "        counter = Counter(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        total = sum(nums)\n",
    "        if l > total: return 0\n",
    "        n = len(counter)\n",
    "        r = min(r, total)\n",
    "        f = [[0] * (r+1) for _ in range(n+1)]\n",
    "        f[0][0] = counter[0] + 1\n",
    "        \n",
    "        if 0 in counter: \n",
    "            n -= 1\n",
    "            del counter[0]\n",
    "        a = [(x, counter[x]) for x in counter]\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(min(r+1,a[i-1][0])):\n",
    "                f[i][j] = f[i-1][j]\n",
    "            \n",
    "            for j in range(a[i-1][0], r+1):\n",
    "                f[i][j] = (f[i][j-a[i-1][0]] + f[i-1][j]) % MOD\n",
    "                if j >= a[i-1][0] * (a[i-1][1] + 1):\n",
    "                    f[i][j] = (f[i][j]- f[i-1][j - a[i-1][0] * (a[i-1][1] + 1)]) % MOD\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(l, r+1):\n",
    "            res = (res + f[n][i]) % MOD \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        #好像是在找子集，多重背包\n",
    "        cnt=Counter(nums)\n",
    "\n",
    "        #dfs(i,j)=dfs(i-1,j)+dfs(i-1,j-x)+...+dfs(i-1,j-c*x)\n",
    "        #其中，cnt[x]=c,x在cnt中排在第i个位置\n",
    "        #前缀和优化呼之欲出\n",
    "        #定义s[j]=f[i-1][j]+f[i-1][j-x]+....,这个叫做同余前缀和,两个式子应保持等长\n",
    "        #那么s[j]=s[j-x]+f[i-1][j]\n",
    "        #f[i][j]=s[j]-s[j-(c+1)*x]\n",
    "\n",
    "        #i的范围会是多少?sqrt(S)\n",
    "        \n",
    "        #什么样的前缀和?\n",
    "        #dfs(i,j-x)=dfs(i-1,j-x)+...+dfs(i-1,j-(c+1)*x)\n",
    "\n",
    "        #dfs(i,j)=dfs(i,j-x)+dfs(i-1,j)-dfs(i-1,j-(c+1)*x)\n",
    "\n",
    "        #还有个要点，元素0怎么处理？\n",
    "        MOD=10**9+7\n",
    "        c0=cnt[0]+1\n",
    "        del cnt[0]\n",
    "        '''\n",
    "        @cache\n",
    "        def dfs(i:int,j:int)->int:\n",
    "            if i==-1:\n",
    "                return c0 if j==0 else 0\n",
    "            if j<0:\n",
    "                return 0\n",
    "            x,c=s[i]\n",
    "            return (dfs(i,j-x)+dfs(i-1,j)-dfs(i-1,j-(c+1)*x))%MOD\n",
    "        '''\n",
    "\n",
    "        s=sum(nums)\n",
    "        f=[[0]*(s+1) for _ in range(len(cnt)+1)]\n",
    "        f[0][0]=c0\n",
    "        for i,(x,c) in enumerate(cnt.items()):\n",
    "            for j in range(s+1):\n",
    "                if j<x:\n",
    "                    f[i+1][j]=f[i][j]\n",
    "                else:\n",
    "                    if j-(c+1)*x<0:\n",
    "                        f[i+1][j]=(f[i+1][j-x]+f[i][j])%MOD\n",
    "                    else:\n",
    "                        f[i+1][j]=(f[i+1][j-x]+f[i][j]-f[i][j-(c+1)*x])%MOD\n",
    "        \n",
    "        return sum(f[-1][l:r+1])%MOD\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
